#define _CRT_SECURE_NO_WARNINGS 1
#include"Huffman.h"


int Min(HuffmanTree t, int n)
{
	int flag = 0;
	int f = SuperMax;
	for (int i = 1; i <= n; i++)
		if (t[i].weight < f && t[i].parent == 0)
			f = t[i].weight, flag = i;
	t[flag].parent = 1;
	return flag;
}

void Select(HuffmanTree* t, int n, int* s1, int* s2)
{
	*s1 = Min(*t, n);
	*s2 = Min(*t, n);
	if ((*t)[*s1].weight > (*t)[*s2].weight)
	{
		int tmp = *s1;
		*s1 = *s2;
		*s2 = tmp;
	}
}
void HuffmanCoding(HuffmanTree* HT, HuffmanCode* HC, int* w, int n)
{
	int s1, s2, i, start;
	int c, f;
	HuffmanTree p = NULL;
	char* cd = NULL;
	if (n <= 1)
		return;
	int m = 2 * n - 1;
	*HT = (HuffmanTree)malloc(sizeof(HTNode) * (m + 1));
	if (!(*HT))
		exit(-1);
	p = *HT + 1;
	for (i = 1; i <= n; i++, p++, w++)
	{
		(*p).weight = *w;
		(*p).parent = 0;
		(*p).lchild = 0;
		(*p).rchild = 0;
	}
	for (; i <= m; i++, p++)
		(*p).parent = 0;
	for (i = n + 1; i <= m; i++)
	{
		Select(HT, i - 1, &s1, &s2);
		(*HT)[s1].parent = (*HT)[s2].parent = i;
		(*HT)[i].lchild = s1;
		(*HT)[i].rchild = s2;
		(*HT)[i].weight = (*HT)[s1].weight + (*HT)[s2].weight;
	}
	*HC = (HuffmanCode)malloc(sizeof(char*) * (n + 1));
	if (!(*HC))
		exit(-1);
	cd = (char*)malloc(n * sizeof(char));
	if (!cd)
		exit(-1);
	cd[n - 1] = '\0';
	for (i = 1; i <= n; i++)
	{
		start = n - 1;
		for (c = i, f = (*HT)[i].parent; f != 0; c = f, f = (*HT)[f].parent)
		{
			if ((*HT)[f].lchild == c)
				cd[--start] = '0';
			else
				cd[--start] = '1';
			(*HC)[i] = (char*)malloc((n - start) * sizeof(char));
			strcpy((*HC)[i], &cd[start]);
		}
	}
	free(cd);
}
